The present invention relates to the field of image rendering. More specifically, in one embodiment the invention provides an improved system for rendering images which takes into account multiple diffuse reflections of light.
The process of deriving an image from a model is called "rendering" the image. The model is typically a geometrical description of a viewpoint, objects, and light sources, and their positions and orientations in a three dimensional space, often referred to as the model space, or "world". Locations in the model space are described by world coordinates, which is contrasted with image coordinates which describe a position in a view of the model space.
One well-known method of rendering an image is the process of "ray-tracing". Ray-tracing is illustrated in FIG. 1, which shows a three dimensional geometric model space 10 containing an object 12 with a surface 14, an object 16 with a surface 18, a light source 20, a view surface 22, and a center of projection, or "view" point, P. View surface 22 is divided into unit areas which have a one-to-one correspondence with pixels of a pixelated display device 24, and the pixels of device 24 collectively form an image of the model space. The image is a view of the model space when looking through view surface 22 from the perspective of view point P.
View surface 22 and the display surface of display 24, for simplicity, are shown as planar surfaces, however they need not be planar. View surface 22 also does not necessarily have to be the same shape as the display surface of display device 24 nor need viewing point P be a constant for all rays passing through view surface 22. Pixelated display device 24 could be a computer graphics monitor, a bit-mappable printer, or a device which stores bit-mapped images for later display.
The goal of ray-tracing, or any rendering process, is to determine color information each pixel in the image, such as exemplary pixel A.sub.ij of an image formed on display device 24 from the collection of pixels displayed on device 24. The color of pixel A.sub.ij depends on what objects and light sources (often referred to just as "objects", with light sources being self-luminous objects, or luminaires) are present in the model space and where they are located in that model space. More particularly, ray tracing determines the color of pixel A.sub.ij by tracing one or more rays, such as ray R', from point P through unit area a.sub.ij on view surface 22 and continuing until an object is encountered. The ray tracer then determines what color of light is given off the intersected object in the direction opposite the ray being traced (shown by ray R). Of course, ray tracing is iterative, in that rays must be sent out from the intersected point to see what light illuminates the intersected point, in order to determine what light is reflected or transmitted in the direction of ray R.
Depending on the implementation, multiple rays R' might be sent out for each unit area, and the resulting color for the multiple rays are combined (by averaging or other means) to arrive at a single color value for the unit area, and thus for the pixel. Aliasing causes edges to appear jagged, or "stair-stepped". Using multiple rays per pixel reduces aliasing, by providing "smoothed" colors in adjacent pixels.
Color can be represented in a number of ways, but is generally reducible to an n-tuple of component color values. The n-tuple of values might be an RGB representation (triplet of red, green, and blue intensities), or CYMK (quartet of cyan, yellow, magenta, and black intensities), or even a 20- or n-tuple of intensities of specific wavelengths covering the visible light spectrum. In rendering processes, color can be treated as an n-tuple or each color component could be processed as a separate monochromatic image.
Color, when used below, refers to the intensity as well as shade, so a specific color could refer to the intensity of lightness or darkness in a monochromatic image, such as a black ink intensity on a printed page, or it could refer to different shades of similar intensity, such as the color red and the color blue-green. Although colors viewed by the human eye might be suitably represented by intensity values of three components, more color components are often needed to accurately model physical effects such as reflections from a surface where the specular energy reflected from the surface is a function of wavelength. The units of color are generally the power per normalized unit of area at the point the light is being measured.
The following discussion will assume that ray R' does intersect an object. This assumption is not limiting, since a "background" object can be provided if needed, to catch all rays which would not otherwise intersect an object. The background object is behind (relative to the view) all the other objects in the model space and occupies the entire view of view surface 22 which is not occupied by other objects in model 10. If the model space has a background at infinity, then a finite background object which gives off no light should be used.
In FIG. 1, the first surface encountered by ray R' is surface 18 of object 16, at the intersection point O. Because the first intersection of ray R' is surface 18 at point O, the color value for pixel A.sub.ij is simply the color of light given off (emitted, reflected, or transmitted) by object 16 at point O along ray R. The light given off by object 16, which is non-self-luminous, is just the light reflected from object 16 at point O and the light transmitted through object 16 at point O. Since reflection and transmission (through the bottom of a fully or partially translucent surface) are handled in nearly identical ways, the discussion herein is in terms of reflection, with the understanding that transmissive effects are also included.
Although ray R' is shown as a line, it is actually a pyramid with an apex at point P and sides defined by the sides of the unit area a.sub.ij (or a portion of the unit area when multiple rays per pixel are traced). However, for small enough unit areas, the pyramid is suitably approximated by a ray through the center of the unit area, or multiple rays distributed over the unit area. Pixel A.sub.ij, which by definition can only have one color value, then has the color value of the light reflected by point O in the direction of ray R, or a suitable combination of the multiple rays passing through A.sub.ij.
Thus, the problem of ray tracing is reduced to finding the color of light reflected off the point O along ray R. The color of light reflected off a point is dependent on the light incident on that point. Because of the iterative nature of shading a point (finding its color), shading points on objects intersected by tracing rays occupies most of the computing power required for rendering an image.
Light reflected by point O is well approximated by a linear combination of a specular reflection and a diffuse reflection, with self-illumination ignored for now. Specular reflection off a point is light directionally reflected in a direction opposite the light incident on the point, i.e., a mirror-type reflection. The light being reflected strikes the surface at a point with a given angle with respect to a normal to that surface at the point, and the reflected light leaves the surface in a direction of a ray which is in the plane defined by the normal and the incident ray, although the reflected ray might be dispersed somewhat. This dispersal can be modelled by the "Phong" illumination model, which approximates the intensity of the specularly reflected light at any angle as a function of the difference between that angle and the angle of the reflected ray (call this quantity .theta.) and which is proportional to cos.sup.n .theta., where n, the specular reflection exponent, is a characteristic of the surface which reflects the light. For higher values of n, the specular qualities of the surface approach a perfect mirror, where a single incident ray results in a single reflective ray. For lower values of n, the surface approaches a diffuse surface.
There is another kind of specular light, refractive light. Refractive light is light which arrives at point O from below surface 18, such as when object 16 is translucent an illuminated from behind. This light is treated as specular light, except that the refractive index of the surface and light sources or lit objects below the surface of the object must be taken into account. This is also known as transmissive reflection. The extension of these concepts to refractive light is straightforward, so refracted light will be ignored for now.
The other type of reflected light, diffuse reflected light, is reflected in all directions evenly, i.e. the intensity in any given direction is not a function of the outgoing direction, only a function of surface properties and the direction and color of the incident light. Objects which do not appear shiny reflect primarily diffuse reflections, whereas shiny objects have more specular reflection. Most real objects have some of both.
As hinted at above, reflected light depends not only on the light incident on the surface, but also depends on what the surface does to the light it is given. The surface converts incident light into specular reflected light, diffusely reflected light, and absorbed light. The absorption of a surface is easily modelled, and as a first approximation, the object's color indicates its absorption. The amounts of a given light which will be specularly reflected and diffusely reflected are also easily modelled.
Thus, from surface characteristics of a point on the surface of an object and the descriptions of all incident light rays on that point, the reflected light from the point can be calculated. To find the reflected light along a specific ray from a point on a surface, such as ray R leaving point O, one needs to know only the light incident on point O from one direction (the specular component), the light incident on point O from all directions (diffuse components), and the surface characteristics at point O. Thus, since diffuse reflections are omnidirectional, a diffusely reflected ray of light which could reflect in the direction of a traced ray could come from anywhere. To find specular reflections in the direction of the traced ray, one only needs to look in one direction (or a small number of directions for dispersed specular reflections), namely the direction of reflection.
FIG. 2 illustrates this point, showing surface 18 of object 16 in greater detail. The light given off of surface 18 in the direction of ray R is the light of interest, and N is a vector normal to surface 18 at point O. The light of interest for calculating the specular reflection in the direction of ray R is found by measuring the light incident on point O from the direction of ray S and factoring in the specular reflection characteristics of the surface (S' is the refractive component) at point O. The light of interest for calculating the diffuse reflections in the direction of ray R is another matter, since the region above the surface 18 must be searched for objects in all directions. Only some of these directions are illustrated by the rays D in FIG. 2. The computation becomes intractable when multiple reflections are considered--to find the color of light arriving at point O from a point on another object, such as point Q on object 12, all the rays of light arriving at point Q must be determined to find the color of light given off by object 12 at point Q in the direction of point O.
The problem of the infinite directions of rays D is simplified somewhat if the point O is visible by only a few points on illuminating objects, but most realistic looking images are complex enough that a means for dealing with the large number of light sources diffusely reflected by a point on a surface is needed. Several solutions to the problem of diffuse reflections have been proposed, but none are entirely satisfactory.
One solution is called the "radiosity" method. With radiosity, every object is divided into finite elements, and starting with the proposition that all light in a closed system is conserved, the light coupling between each finite element and each other finite element is calculated. Then, to calculate the image, the light sources illuminate all the finite elements in their field in a first pass, and then the light is coupled to other finite elements in subsequent passes, with some arbitrary limit on the number of iterations. After the radiosity of each finite element is calculated, a view point (center of projection) and a view plane are placed in the modelling space, and rays from the view point through the unit areas of the view plane are intersected with finite elements. The radiosity of an intersected finite element indicates the color of the pixel associated with that unit area.
The problem with radiosity methods is that the division of object surfaces into finite elements is an art. If the finite elements are too small, computation time is wasted, and if the finite elements are too large, the final image might appear with jagged edges (aliasing). Even with the proper division of surfaces into finite elements, computation time might be wasted calculating radiosity parameters for points of surfaces which are not visible in the desired view plane from the desired view point.
Another proposed solution is to ignore the effect of diffuse reflections from points such as point Q when determining the light incident on point O. This simplifies the calculations in many cases, since most points will appear black to point O, and only the light sources and rays of specular reflection directed at point O need to be considered. Of course, in a model space containing light sources and two objects with diffuse surfaces, no light from one object would reflect off the other. FIG. 3 illustrates the error caused by this simplification.
FIG. 3 is a model space 48, which has a light source 50 directly illuminating a wall 52 and an enclosure 54, each of which are not translucent and have diffusely reflecting surfaces facing light source 50. Wall 52 blocks light source 54 from direct view at a view point V. Another wall 56 is located behind enclosure 54 with respect to view point V and also has a diffuse surface which faces enclosure 54 and view point V. Suppose light source 50 outputs white light, the surface of enclosure 54 visible from light source 50 is black, the surface of wall 52 visible from light source 50 is red, and the surface of wall 56 facing enclosure 54 and view point V is white. In such a model, light from light source 50 will reach view point V only through two (or more) diffuse reflections along a path such as paths P, and the light reaching view point V is red. Given the geometry of model 48, specular reflections off wall 52 and then off wall 56 cannot reach view point V.
In the above example, a rendered image of model 48 will appear completely black if multiple diffuse reflections are ignored. A correct rendering is one in which the visible portion of wall 56 (area 58) is shaded with various intensities of red, the red light being brightest near the edge of wall 52.
One method of accounting for the elimination of multiple diffuse reflections in a rendering is to add in an "ambient" light source. The model for ambient light is a constant color light striking an object from an unspecified angle and diffusely reflecting from that object. Ambient light, however, does not account for the interplay of light off various objects in a model and the subtle shadings in shadows. In the example of FIG. 3, the ambient light would not necessarily be red, so area 58 would appear to be whatever color is chosen for the ambient light. Furthermore, the side of wall 52 visible from view point V would be lit by the ambient light, when wall 52 is totally dark in a correct rendering.
Ward [Ward, G. J., "A Ray Tracing Solution for Diffuse Interreflection", Computer Graphics, Vol. 22, No. 4, August 1988, pp. 85-92] presents a method of averaging indirect illumination (light from non-self-luminous surfaces) incident on a surface. At the start of a rendering, the indirect illumination at a point is calculated, used in the ray tracing process and then stored. When calculating the illumination of a point nearby the first point, the indirect illumination values stored for the first point are used for the nearby point, if the nearby point is "close enough" to the first point.
As calculations are done for points, the points are given weights which indicate the span of the surface around the points over which their calculated indirect illumination values might be usable, and for some points, a weighted average of indirect illumination values of multiple nearby points is used. Thus, at the beginning of the rendering, most points are evaluated by the primary process in which indirect illumination is calculated for the point and stored, and later in the rendering, more points are evaluated using a secondary process in which stored values are averaged from values stored during the primary process for nearby points.
One of the drawbacks of such a system is with models having rapidly changing light sources, which allows fewer evaluations to be done using the secondary process. At the limit, indirect illumination values are calculated at every point using the primary process and none of these calculations are reused at other points in the secondary process.
Further efficiencies in computing diffuse reflection contributions are still needed. Ward suggests that after some number of reflections, the light be replaced with an ambient light term, to limit the number of calculations. While this may be an improvement over the prior method of treating all reflections beyond the first diffuse bounce as ambient light, an improved method and apparatus for quickly rendering an image of a geometrical model in a defined space is still needed.